#include "OS_specific_dependencies.h"

#include<cstdlib>
#include<string>
#include<iostream>
#include<sstream>
#include<queue>
#include<map>

using namespace std;

const int dim = 30;
const int SCR_W = 660;
const int SCR_H = 510;
const int SCR_BPP = 32; // bits per pixel
const double FRAMES_PER_SECOND = 120;
bool start = 0;
bool stop = 0;

SDL_Surface *screen = NULL;
SDL_Surface *scores = NULL; 
SDL_Color bgcolor = {0, 0, 0};
SDL_Event eve;
TTF_Font *font = NULL; 
SDL_Color textColor = { 255, 255, 255 }; 

SDL_Surface* load_image(string filename);
void apply_surface(int x, int y, SDL_Surface *source, SDL_Surface *destination, SDL_Rect* Clip = NULL);
void print_score(int);
void print_message(char*);



class labyrinth
{
	/* kodirane:	0 - nishto
					1 - tochka
					2 - stena
					3 - chervena tochka
	*/
	int ground[SCR_H/dim-1][SCR_W/dim];
	SDL_Surface *dot;
	SDL_Surface *redDot;
	SDL_Surface *brick;
	int dotCount;
	
	void drawTile(int i, int j)
	{
		if(ground[i][j] == 1)
				{
					apply_surface(j*dim, i*dim, dot, screen);
					
				}
				else if(ground[i][j] == 2)
					apply_surface(j*dim, i*dim, brick, screen);
				else if(ground[i][j] == 3)
				{
					apply_surface(j*dim, i*dim, redDot, screen);
					
				}
				else
				{
					SDL_Rect r;
					r.x = j*dim;
					r.y = i*dim;
					r.w = dim;
					r.h = dim;
					SDL_FillRect( screen, &r, SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
				}


	}
	
public:
	labyrinth(int bitmap[SCR_H/dim-1][SCR_W/dim], char *dotName, char *brickName, char * redName)
	{
		for(int i=0;i<SCR_H/dim-1;i++)
			for(int j=0;j<SCR_W/dim;j++)
				ground[i][j]=bitmap[i][j];
		dot = load_image(dotName);
		if(dot == NULL)
		{
			cout<<"Unable to load dot image: "<<dotName<<". Quitting."<<endl;
			exit(1);
		}
		brick = load_image(brickName);
		if(brick == NULL)
		{
			cout<<"Unable to load brick image: "<<brickName<<". Quitting."<<endl;
			exit(1);
		}
		redDot = load_image(redName);
		if(redDot == NULL)
		{
			cout<<"Unable to load red dot image: "<<redName<<". Quitting."<<endl;
			exit(1);
		}
		dotCount = 0;
		for(int i=0;i<SCR_H/dim-1;i++)
			for(int j=0;j<SCR_W/dim;j++)
			{
				drawTile(i,j);
				if(ground[i][j]==1||ground[i][j]==3)
					dotCount++;
			}
	}
	~labyrinth()
	{
		SDL_FreeSurface(dot);
		SDL_FreeSurface(brick);
		SDL_FreeSurface(redDot);
	}
	bool checkBrick(int x, int y)
	{
		if(ground[(y+dim-1)/dim][(x+dim-1)/dim]==2||ground[y/dim][(x+dim-1)/dim]==2||ground[(y+dim-1)/dim][x/dim]==2||ground[y/dim][x/dim]==2)
			return true;
		return false;
	}
	void checkDot(int x, int y, int& dots, int & red)
	{
		dots = red = 0;
		int check[4][2] = { {(y+dim/2), (x)},
                            {(y+dim/2),(x+dim-1)},
                            {(y),(x+dim/2)},
                            {(y+dim-1),(x+dim/2)}};
    
        for(int z=0;z<4;z++)
        {
			int x1=check[z][0];
			int y1 = check[z][1];
            if(ground[x1/dim][y1/dim]==1&&x1%dim>dim/3&&x1%dim<2*dim/3&&y1%dim>dim/3&&y1%dim<2*dim/3)
            {
                ground[x1/dim][y1/dim] = 0;
                dotCount--;
                dots++;
            }
			else if(ground[x1/dim][y1/dim]==3&&x1%dim>dim/3&&x1%dim<2*dim/3&&y1%dim>dim/3&&y1%dim<2*dim/3)
			{
				ground[x1/dim][y1/dim] = 0;
                dotCount--;
                red++;
			}

        }
		
		if(!dotCount)
		{
			print_message("You won. Bravo!");
			stop = 1;
		}

	
	}
	void drawTiles(int x, int y)
	{
		drawTile(y/dim, x/dim);
		drawTile((y/dim)+1, x/dim);
		drawTile((y/dim), x/dim+1);
		drawTile((y/dim)+1, x/dim+1);
	}
	void eatTiles(int x, int y, int &dots, int &red)
	{
		checkDot(x,y,dots, red );
		drawTiles(x,y);
		
	}


};


class creature
{
protected:
	SDL_Rect coords;
	int started[2];
	 
	SDL_Surface *img;  
	labyrinth *ground;
	virtual void step() = 0; //izchislqwa nowite koordinati na plochkata
	virtual void checkEat(){}
	
public:
	creature(int x1, int y1, int e, char * name,labyrinth *lab)
	{
		coords.x=x1*dim;
		coords.y=y1*dim;
		coords.w=dim;
		coords.h=dim;
		started[0]=x1*dim;
		started[1]=y1*dim;

		img = load_image(name);
		if(img == NULL)
		{
			cout<<"Unable to load the creature image: "<<name<<". Quitting."<<endl;
			exit(1);
		}
		ground = lab;
		eaten = 0;
	}
	virtual ~creature()
	{
		if(img!=NULL)
			SDL_FreeSurface(img);
	}
	SDL_Rect getcoords()
	{
		return coords;
	}
	
	void move()
	{
		if(stop)
			return;
		
		SDL_FillRect( screen, &coords, SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
		
		step();
		apply_surface( coords.x, coords.y, img, screen);
		checkEat();
		
	}
	virtual void reset()
	{
		eaten = false;
		coords.x = started[0];
		coords.y = started[1];
	}
	bool eaten;
	bool eat;
};

class  bonus:public creature
{
	
	int direction[2];
	void setDirection()
	{
		int temp;
		temp =rand()%4;
		direction[0] = ((temp%2)?1:(-1));
		direction[1] = 0;
		if(temp/2)
			swap(direction[0],direction[1]);
	}
	
	void step()
	{
		if(eaten)
			return;
		
		ground->drawTiles(coords.x,coords.y);
		if(!(rand()%200))
		{
			setDirection();
		}
		int x1,y1;
		x1=coords.x+2*direction[0];
		y1=coords.y+2*direction[1];
		
		if(ground->checkBrick(x1,y1))
		{
			setDirection();
			
		}
		else 
		{
			coords.x=x1;
			coords.y=y1;
			
		}
	}
public:

	bonus(int x1, int y1, int e, labyrinth *lab,char *name = "images/cherry.jpg"):creature(x1,y1,e,name,lab)
	{
		eaten=0;
		setDirection();
		
	}

};

class  pacman:public creature
{
	int direction[2];
	int trying[2];
	int score;
	bonus *cherry;
	int timeToScare;
	
	
	void step()
	{
		if(eaten)
			return;
		
		if(timeToScare)
			timeToScare--;
		else
			eat = false;
		int dots, red;
		ground->eatTiles(coords.x,coords.y, dots, red);
		score +=dots + red;
		if(dots + red>0&&!stop)
			print_score(score);
		if(red > 0)
		{
			eat = 1;
			timeToScare = 800;
		}
		int x1,y1;
		x1=coords.x+3*trying[0];
		y1=coords.y+3*trying[1];
		
		if(ground->checkBrick(x1,y1))
		{
			x1=coords.x+3*direction[0];
			y1=coords.y+3*direction[1];
			if(!ground->checkBrick(x1,y1))
			{
				coords.x = x1;
				coords.y = y1;
			}
			
		}
		else 
		{
			direction[0] = trying[0];
			direction[1] = trying[1];
			coords.x=x1;
			coords.y=y1;
		}
	}
	bool pointin(int x,int y)
	{
		
		if((x>=coords.x)&&(x<coords.x+dim)&&(y>=coords.y)&&(y<coords.y+dim))
			return true;
		return false;
	}
	void checkEat()
	{
		
		
		if(cherry->eaten)
			return;
		int x1 = cherry->getcoords().x;
		int y1 = cherry->getcoords().y;
		if(cherry && (pointin(x1,y1)||pointin(x1,y1+dim)||pointin(x1+dim,y1)||pointin(x1+dim,y1+dim)))
		{
			cherry->eaten = 1;
			SDL_FillRect( screen, &cherry->getcoords(), SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
			score +=100;
			print_score(score);
			
			
		}

	}
public:
	pacman(int x1, int y1, int e, labyrinth *lab,bonus* cherry1, char *name = "images/pac.jpg"):creature(x1,y1,e,name,lab)
	{
		for(int i=0;i<2;i++)
			direction[i] = trying[i] = 0;
		cherry = cherry1;
		score = 0;
		timeToScare = 0;
	}
	
	void setx(int t)
	{
		trying[0] = (t>0)?1:(-1);
		trying[1] = 0;
	}
	void sety(int t)
	{
		trying[1] = (t>0)?1:(-1);
		trying[0] = 0;
	}
	void reset()
	{
		creature::reset();
		direction[0]= direction[1] = 0;
		trying[0] = trying[1] = 0;
	}
};


class monster: public creature
{
protected:
	int direction[4][2];
	pacman *pac;
	bool scared;
	SDL_Surface *calm;
	SDL_Surface *fear;
	SDL_Surface *eyes;
public:
	monster(int x1, int y1, int e, labyrinth *lab,pacman* pac1,char *n1, char *n2,char *n3 ):creature(x1,y1,e,n1,lab)
	{
		calm = load_image(n1);
		fear = load_image(n2);
		eyes = load_image(n3);
		
		direction[0][0] = 1;
		direction[0][1] = 0;
		direction[1][0] = -1;
		direction[1][1] = 0;
		direction[2][0] = 0;
		direction[2][1] = 1;
		direction[3][0] = 0;
		direction[3][1] = -1;
		scared = 0;
		eaten = 0;
		pac = pac1;
	}
	virtual ~monster()
	{
		img = NULL; // za da ne moje da se iztrie i ot creature. Kartinkata, kym koqto sochi, e ili calm, ili scared, ili eyes.
		if(calm)
			SDL_FreeSurface(calm);
		if(fear)
			SDL_FreeSurface(fear);
		if(eyes)
			SDL_FreeSurface(eyes);
	}
	void beScared()
	{
		scared = true;
		img = fear;
	}
	void calmDown()
	{
		if(! eaten)
		{
			scared = false;
			img = calm;
		}
	}
	virtual void reset()
	{
		ground->drawTiles(coords.x,coords.y);
		eaten = false;
		scared = false;
		coords.x = started[0];
		coords.y = started[1];
		img = calm;
		pac->eat = false;
		creature::reset();		
	}
};

class clyde:public monster
{
	void moveto(int x, int y,int runaway = 0)
	{
		long long x1,y1;
		int t=4;
		if(runaway)
		{
			
			long long max = (x-coords.x)*(x-coords.x) + (y-coords.y)*(y-coords.y);
			for(int i = 0;i<4;i++)
			{
				x1 = coords.x + 2*direction[i][0];
				y1 = coords.y + 2*direction[i][1];
				if(!ground->checkBrick(x1,y1))
					if(max<(x-x1)*(x-x1) + (y-y1)*(y-y1))
					{
						max = (x-x1)*(x-x1) + (y-y1)*(y-y1);
						t = i;
					}
			}
			
		}
		else
		{
			
			long long min =(x-coords.x)*(x-coords.x) + (y-coords.y)*(y-coords.y);
			for(int i = 0;i<4;i++)
			{
				x1 = coords.x + 2*direction[i][0];
				y1 = coords.y + 2*direction[i][1];
				if(!ground->checkBrick(x1,y1))
					if(min>(x-x1)*(x-x1) + (y-y1)*(y-y1))
					{
						min = (x-x1)*(x-x1) + (y-y1)*(y-y1);
						t = i;
					}
			}
		}
		if(t<4)
		{
			
			coords.x += 2*direction[t][0];
			coords.y += 2*direction[t][1];
		}
	}
	void step()
	{
		if(!start)
			return ;
		if(pac->eaten)
		{
			reset();
		}
		else
		{
			ground->drawTiles(coords.x,coords.y);
			if(eaten)
			{
				img = eyes;
				if(coords.x ==9*dim&&coords.y == 9*dim)
				{
					reset();

				}
				else moveto(9*dim,9*dim);
			}
			else if(scared)
				moveto(pac->getcoords().x, pac->getcoords().y, 1);
			else
				moveto(pac->getcoords().x, pac->getcoords().y);
		}
	
	}
	bool pointin(int x,int y)
	{
		
		if((x>=coords.x)&&(x<coords.x+dim)&&(y>=coords.y)&&(y<coords.y+dim))
			return true;
		return false;
	}
	void checkEat()
	{
		
		if(!pac || pac ->eaten)
			return;
		int x1 = pac->getcoords().x;
		int y1 = pac->getcoords().y;
		if(pointin(x1,y1)||pointin(x1,y1+dim)||pointin(x1+dim,y1)||pointin(x1+dim,y1+dim))
		{
			if(!scared && !eaten)
			{
				start = 0;
				pac->eaten = 1;
				SDL_FillRect( screen, &pac->getcoords(), SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
			}
			else
			{
				eaten = true;
				img = eyes;
			}
		
		}
		

	}
public:
	clyde(int x1, int y1, int e, labyrinth *lab,pacman* pac1,char *n1 = "images/clyde.jpg", char *n2 = "images/fear.jpg",char *n3 = "images/eyes.jpg" ):monster(x1,y1,e,lab,pac1,n1,n2,n3)
	{}

};



class inky:public monster
{
	int dir1[2];
	int timeStill;
	int timeRandom;
	bool scared;
	void moveto(int x, int y,int runaway = 0)
	{
		
		long long x1,y1;
		int t=4;
		if(runaway)
		{
			
			long long max = (x-coords.x)*(x-coords.x) + (y-coords.y)*(y-coords.y);
			for(int i = 0;i<4;i++)
			{
				x1 = coords.x + 2*direction[i][0];
				y1 = coords.y + 2*direction[i][1];
				if(!ground->checkBrick(x1,y1))
					if(max<(x-x1)*(x-x1) + (y-y1)*(y-y1))
					{
						max = (x-x1)*(x-x1) + (y-y1)*(y-y1);
						t = i;
					}
			}
			
		}
		else
		{
			
			long long min =(x-coords.x)*(x-coords.x) + (y-coords.y)*(y-coords.y);
			for(int i = 0;i<4;i++)
			{
				x1 = coords.x + 2*direction[i][0];
				y1 = coords.y + 2*direction[i][1];
				if(!ground->checkBrick(x1,y1))
					if(min>(x-x1)*(x-x1) + (y-y1)*(y-y1))
					{
						min = (x-x1)*(x-x1) + (y-y1)*(y-y1);
						t = i;
					}
			}
		}
		if(t<4)
		{
			
			coords.x += 2*direction[t][0];
			coords.y += 2*direction[t][1];
		}
		else
			timeStill++;
	}
	void setDirection()
	{
		int temp;
		temp =rand()%4;
		dir1[0] = ((temp%2)?1:(-1));
		dir1[1] = 0;
		if(temp/2)
			swap(dir1[0],dir1[1]);
	}
	void moveRandom()
	{
		timeStill = 0;
		
		int x1,y1;
		x1=coords.x+2*dir1[0];
		y1=coords.y+2*dir1[1];
		
		if(ground->checkBrick(x1,y1))
		{
			setDirection();
			timeStill++;
			
		}
		else 
		{
			coords.x=x1;
			coords.y=y1;
			
		}
	}

		
	void step()
	{
		
		if(!start)
			return ;
		if(pac->eaten)
		{
			reset();
		}
		else
		{
			ground->drawTiles(coords.x,coords.y);
			if(eaten)
			{
				img = eyes;
				if(coords.x ==12*dim&&coords.y == 9*dim)
				{
					reset();

				}
				else if(timeStill>30)
					{
						//setDirection();
						timeStill = 0;
						timeRandom = 100;
					}
				else if(timeRandom >0)
				{
					timeRandom --;
					
					moveRandom();
				}
				else moveto(12*dim,9*dim);
			}
			else if(timeStill>30)
			{
				//setDirection();
				timeStill = 0;
				timeRandom = 100;
			}
			else if(timeRandom >0)
			{
				timeRandom --;
				moveRandom();
			}
			else if(scared)
				moveto(pac->getcoords().x, pac->getcoords().y, 1);
			else
				moveto(pac->getcoords().x, pac->getcoords().y);
		}
		



		
	}
	bool pointin(int x,int y)
	{
		
		if((x>=coords.x)&&(x<coords.x+dim)&&(y>=coords.y)&&(y<coords.y+dim))
			return true;
		return false;
	}
	void checkEat()
	{
		
		if(pac ->eaten)
			return;
		int x1 = pac->getcoords().x;
		int y1 = pac->getcoords().y;
		if(pointin(x1,y1)||pointin(x1,y1+dim)||pointin(x1+dim,y1)||pointin(x1+dim,y1+dim))
		{
			if(!scared && !eaten)
			{
				start = 0;
				pac->eaten = 1;
				SDL_FillRect( screen, &pac->getcoords(), SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
			}
			else
			{
				eaten = true;
				img = eyes;
			}
		
		}
		

	}

public:
	inky(int x1, int y1, int e, labyrinth *lab,pacman* pac1,char *n1 = "images/inky.jpg", char *n2 = "images/fear.jpg",char *n3 = "images/eyes.jpg" ):monster(x1,y1,e,lab,pac1,n1,n2,n3)
	{
		setDirection();
		timeStill = 0;
		timeRandom = 0;	
	}
	void reset()
	{
		monster::reset();
		timeStill = 0;
		timeRandom = 0;
	}
};





class  pinky:public monster
{
	int dir1[2];
	int timeStill;
	int timeRandom;
	void moveto(int x, int y,int runaway = 0)
	{
		
		long long x1,y1;
		int t=4;
		if(runaway)
		{
			
			long long max = (x-coords.x)*(x-coords.x) + (y-coords.y)*(y-coords.y);
			for(int i = 0;i<4;i++)
			{
				x1 = coords.x + 2*direction[i][0];
				y1 = coords.y + 2*direction[i][1];
				if(!ground->checkBrick(x1,y1))
					if(max<(x-x1)*(x-x1) + (y-y1)*(y-y1))
					{
						max = (x-x1)*(x-x1) + (y-y1)*(y-y1);
						t = i;
					}
			}
			
		}
		else
		{
			
			long long min =(x-coords.x)*(x-coords.x) + (y-coords.y)*(y-coords.y);
			for(int i = 0;i<4;i++)
			{
				x1 = coords.x + 2*direction[i][0];
				y1 = coords.y + 2*direction[i][1];
				if(!ground->checkBrick(x1,y1))
					if(min>(x-x1)*(x-x1) + (y-y1)*(y-y1))
					{
						min = (x-x1)*(x-x1) + (y-y1)*(y-y1);
						t = i;
					}
			}
		}
		if(t<4)
		{
			
			coords.x += 2*direction[t][0];
			coords.y += 2*direction[t][1];
		}
		else
			timeStill++;
	}
	void setDirection()
	{
		int temp;
		temp =rand()%4;
		dir1[0] = ((temp%2)?1:(-1));
		dir1[1] = 0;
		if(temp/2)
			swap(dir1[0],dir1[1]);
	}
	void moveRandom()
	{
		timeStill = 0;
		if(!(rand()%200))
		{
			setDirection();
		}
		int x1,y1;
		x1=coords.x+2*dir1[0];
		y1=coords.y+2*dir1[1];
		
		if(ground->checkBrick(x1,y1))
		{
			setDirection();
			timeStill++;
			
		}
		else 
		{
			coords.x=x1;
			coords.y=y1;
			
		}
	}

		
	void step()
	{
		
		if(!start)
			return ;
		if(pac->eaten)
		{
			reset();
		}
		else
		{
			ground->drawTiles(coords.x,coords.y);
			if(eaten)
			{
				img = eyes;
				if(coords.x ==12*dim&&coords.y == 7*dim)
				{
					reset();

				}
				else if(timeStill>30)
					{
						//setDirection();
						timeStill = 0;
						timeRandom = 100;
					}
				else if(timeRandom >0)
				{
					timeRandom --;
					
					moveRandom();
				}
				else moveto(12*dim,7*dim);
			}
			else if(timeStill>30)
			{
				//setDirection();
				timeStill = 0;
				timeRandom = 100;
			}
			else if(timeRandom >0)
			{
				timeRandom --;
				moveRandom();
			}
			else if(scared)
				moveto(pac->getcoords().x, pac->getcoords().y, 1);
			else
				moveto(pac->getcoords().x, pac->getcoords().y);
		}
		



		
	}
	bool pointin(int x,int y)
	{
		
		if((x>=coords.x)&&(x<coords.x+dim)&&(y>=coords.y)&&(y<coords.y+dim))
			return true;
		return false;
	}
	void checkEat()
	{
		
		if(pac ->eaten)
			return;
		int x1 = pac->getcoords().x;
		int y1 = pac->getcoords().y;
		if(pointin(x1,y1)||pointin(x1,y1+dim)||pointin(x1+dim,y1)||pointin(x1+dim,y1+dim))
		{
			if(!scared && !eaten)
			{
				start = 0;
				pac->eaten = 1;
				SDL_FillRect( screen, &pac->getcoords(), SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
			}
			else
			{
				eaten = true;
				img = eyes;
			}
		
		}
		

	}
public:
	pinky(int x1, int y1, int e, labyrinth *lab,pacman* pac1,char *n1 = "images/pinky.jpg", char *n2 = "images/fear.jpg",char *n3 = "images/eyes.jpg" ):monster(x1,y1,e,lab,pac1,n1,n2,n3)
	{
		setDirection();
		timeStill = 0;
		timeRandom = 0;		
	}

	void beScared()
	{
		scared = true;
		img = fear;
	}
	void calmDown()
	{
		if(! eaten)
		{
			scared = false;
			img = calm;
		}
	}
	void reset()
	{
		monster::reset();
		timeStill = 0;
		timeRandom = 0;
	}
	
};



class  blinky:public monster
{
	bool checkPac(int x,int y) // dali tochkata (x,y) se namira vyv poleto na pac.
	{
		int p = pac->getcoords().x;
		int q = pac->getcoords().y;

		if((x>=p)&&(x<p+dim)&&(y>=q)&&(y<q+dim))
			return true;
		return false;
	}
	int getDist(int x, int y, int x1, int y1)
	{
		
		return (x - x1)*(x - x1) + (y - y1)*(y - y1);
	}
	void moveto(int x, int y,int runaway = 0)
	{
		
		int w = SCR_W;
		int h = SCR_H-dim;
		if(runaway) // namira ygyl, kojto e naj-daleche ot (x,y). Novata tochka (x,y) e tozi ygyl
		{
			if(coords.x/dim>=9 && coords.x/dim <13 && coords.y/dim >=7 &&coords.y/dim <10)
			{
				x = 10*dim + dim /2;
				y = 7*dim-1;
				//cout<<"in"<<endl;
			}

			else if(coords.x/dim>=10 && coords.x/dim <12 &&coords.y>5*dim && coords.y/dim<7)
			{
				x = 10 * dim + dim /2;
				y = 5*dim;
				//cout<<"pred"<<endl;
				
			}
			else if(coords.y == 5 *dim)
			{
				if(x > SCR_W/2)
					x = 0;
				else
					x = SCR_W - 1;
				y= coords.y;
			}

			else
			{
				if(x > SCR_W/2)
					x = 0;
				else
					x = SCR_W - 1;
				if(y > (SCR_H-dim)/2)
					y = 0;
				else
					y = SCR_H - dim - 1;
				//cout<<"daleche"<<endl;
			}
		}
	
		int mindist = getDist(coords.x, coords.y,x,y);
		int minx = coords.x;
		int miny = coords.y;
		vector<vector<int> > used(660);
		for(int i = 0;i<660;i++)
			used[i].resize(480, 0);

		used[coords.x][coords.y] = -1;
		
		queue<pair<pair<int,int>,int> > bfs; 
		bfs.push(make_pair(make_pair(coords.x,coords.y), 0));
		while(!bfs.empty())
		{
			//if(bfs.size()> 1000)
				//cout<<bfs.size()<<endl;
			pair<pair<int,int>,int> current = bfs.front();
			bfs.pop();
			pair<int,int> temp = current.first;
			if(current.second>90)
				continue;
			for(int i = 0;i<4;i++)
			{
				int x1 = temp.first + direction[i][0];
				int y1 = temp.second + direction[i][1];
				//cout<<x1<<" "<<y1<<endl;
				if(!used[x1][y1]&&!ground->checkBrick(x1,y1))
				{
					
					if(mindist > getDist (x1, y1, x, y))
					{
						mindist = getDist(x1, y1, x, y);
						minx = x1;
						miny = y1;						
					}

					used[x1][y1] = i+1;
					bfs.push(make_pair(make_pair(x1,y1), current.second + 1));
				}
			}
	
		}
		if(mindist == getDist(coords.x, coords.y,x,y))
			return;
		int res = 0;
		while(used[minx][miny]!=-1)
		{
			res = used[minx][miny];
			res --;
			minx+=direction[3-res][0];
			miny+=direction[3-res][1];
		}
		coords.x += 2*direction[res][0];
		coords.y += 2*direction[res][1];
		//cout<<res<<" "<<coords.x<<" "<<coords.y<<endl;
		}

	
	void step()
	{
		
		if(!start)
			return ;
		if(pac->eaten)
		{
			reset();
		}
		else
		{
			
			ground->drawTiles(coords.x,coords.y);
			if(eaten)
			{
				img = eyes;
				if(coords.x ==9*dim&&coords.y == 7*dim)
				{
					reset();

				}
				else moveto(9*dim,7*dim);
			}
			else if(scared)
				moveto(pac->getcoords().x, pac->getcoords().y, 1);
			else
			{
				
				moveto(pac->getcoords().x, pac->getcoords().y);
			}
		}
		



		
	}
	bool pointin(int x,int y)
	{
		
		if((x>=coords.x)&&(x<coords.x+dim)&&(y>=coords.y)&&(y<coords.y+dim))
			return true;
		return false;
	}
	void checkEat()
	{
		
		if(pac ->eaten)
			return;
		int x1 = pac->getcoords().x;
		int y1 = pac->getcoords().y;
		if(pointin(x1,y1)||pointin(x1,y1+dim)||pointin(x1+dim,y1)||pointin(x1+dim,y1+dim))
		{
			if(!scared && !eaten)
			{
				start = 0;
				pac->eaten = 1;
				SDL_FillRect( screen, &pac->getcoords(), SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
			}
			else
			{
				eaten = true;
				img = eyes;
			}
		
		}
		

	}
public:
	//monster(x1, y1, e, lab,pac1,n1 ,n2,n3 )
	blinky(int x1, int y1, int e, labyrinth *lab,pacman* pac1,char *n1 = "images/blinky.jpg", char *n2 = "images/fear.jpg",char *n3 = "images/eyes.jpg" ):monster(x1, y1, e, lab,pac1,n1 ,n2,n3 )
	{		
		direction[0][0] = 1;
		direction[0][1] = 0;
		direction[1][0] = 0;
		direction[1][1] = 1;
		direction[2][0] = 0;
		direction[2][1] = -1;
		direction[3][0] = -1;
		direction[3][1] = 0;
	}

	void reset()
	{
		monster::reset();
	}
	
};





SDL_Surface* load_image(string filename)
{
	SDL_Surface *loaded_image = NULL;
	SDL_Surface *optimised_image = NULL;
	loaded_image = IMG_Load(filename.c_str());
	if(loaded_image!=NULL)
	{
		optimised_image = SDL_DisplayFormat(loaded_image);
		SDL_FreeSurface(loaded_image);
		if(optimised_image!=NULL)
		{
			Uint32 colorkey = SDL_MapRGB(optimised_image->format, 0, 0, 0);
			SDL_SetColorKey(optimised_image, SDL_RLEACCEL|SDL_SRCCOLORKEY, colorkey);
		}
	}

	return optimised_image;
}

void apply_surface(int x, int y, SDL_Surface *source, SDL_Surface *destination, SDL_Rect* Clip)
{
	SDL_Rect offset;
	offset.x=x;
	offset.y=y;
	SDL_BlitSurface(source, Clip, destination, &offset);
}

bool init()
{
	if(SDL_Init( SDL_INIT_EVERYTHING )==-1)
	{
		cout<<"SDL_Init failed!"<<endl;
	    return false;
    }
	screen = SDL_SetVideoMode(SCR_W, SCR_H, SCR_BPP, SDL_SWSURFACE);
    if(screen==NULL)
    {
	    cout<<"SDL_SetVideoMode failed!"<<endl;
	    return false;
    }

    SDL_WM_SetCaption("Pacman", NULL);	

	if( TTF_Init() == -1 ) 
	{
		return false;
	}


	return true;
}

bool load_files()
{	
	return true;
}
void clean_up()
{
	TTF_CloseFont( font ); 
	TTF_Quit(); 
	SDL_Quit();
}
void print_score(int score)
{
	stringstream out;
	out<<"Scores: "<<score;
	scores = TTF_RenderText_Solid( font, out.str().c_str(), textColor );
	SDL_Rect r;
	r.x = 0;
	r.y = SCR_H - dim;
	r.w = SCR_W;
	r.h = dim;
	SDL_FillRect( screen, &r, SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
	apply_surface( SCR_W/2 - 70, SCR_H - dim, scores, screen );
}
void print_message(char* msg)
{
	
	scores = TTF_RenderText_Solid( font, msg, textColor );
	SDL_Rect r;
	r.x = 0;
	r.y = SCR_H - dim;
	r.w = SCR_W;
	r.h = dim;
	SDL_FillRect( screen, &r, SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
	apply_surface( SCR_W/2 - 70, SCR_H - dim, scores, screen );
}

int main(int argc, char* argv[])
{
	
  //freopen("output.txt","w",stdout);
  if((!init()))
  {
	  cout<<"Unable to initialize SDL. Quitting."<<endl;
	  return 1;
  }
  
  
  SDL_FillRect( screen, &screen->clip_rect, SDL_MapRGB( screen->format, bgcolor.r, bgcolor.g, bgcolor.b));
  font = TTF_OpenFont( "lazy.ttf", 28 ); 
  print_message("Scores: 0");

  int bitmap[16][22] = {
					{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},
					{2,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,2},
					{2,1,2,2,1,2,1,2,1,2,2,2,2,1,2,1,2,1,2,2,1,2},
					{2,1,2,1,1,2,2,2,1,1,1,1,1,1,2,2,2,1,1,2,1,2},
					{2,1,1,1,2,2,1,2,1,2,2,2,2,1,2,1,2,2,1,1,1,2},
					{2,1,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,1,2},
					{2,1,2,1,2,1,2,1,2,2,0,0,2,2,1,2,1,2,1,2,1,2},
					{2,1,1,1,1,1,2,1,2,0,0,0,0,2,1,2,1,1,1,1,1,2},
					{2,1,2,1,2,1,2,1,2,0,0,0,0,2,1,2,1,2,1,2,1,2},
					{2,1,2,1,2,1,2,1,2,0,0,0,0,2,1,2,1,2,1,2,1,2},
					{2,1,2,1,2,1,2,1,2,2,2,2,2,2,1,2,1,2,1,2,1,2},
					{2,1,1,1,2,1,1,1,1,1,2,2,1,1,1,1,1,2,1,1,1,2},
					{2,1,2,1,1,1,2,2,2,1,1,1,1,2,2,2,1,1,1,2,1,2},
					{2,1,2,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,2,1,2},
					{2,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,2},
					{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},
				};
labyrinth lab(bitmap, "images/dot.jpg","images/brick1.jpg", "images/reddot.jpg");
bonus cherry (14,11,0, &lab);
pacman pac (3,1,0, &lab, &cherry);
clyde cly(9,9,1, &lab, &pac);
inky ink(12,9,1, &lab, &pac);
pinky pink(12,7,1, &lab, &pac);
blinky blink(9,7,1, &lab, &pac);
  
  double startTimer = 0;
  double stopTimer = 0;
  if(SDL_Flip(screen)==-1)
  {
	  cout<<"SDL_Flip failed!";
	  exit(1);
  }
  

  startTimer = SDL_GetTicks();
  
  bool quit = false;
  start = stop = 0;
  while(!quit)
  {
	  	  
	  
	  stopTimer  = SDL_GetTicks();
	  if(stopTimer - startTimer > 1000.0/FRAMES_PER_SECOND)
	  {
		  startTimer = stopTimer;
		  if(pac.eaten)
		  {
			 pac.reset();
			 cherry.reset();
			 cly.reset();
			 ink.reset();
			 pink.reset();
			 blink.reset();
		  }	
		  if(!(rand()%100)&&cherry.eaten)
		  {
			  cherry.reset();
			 
		  }
		  if(!cherry.eaten)
		  {
			  cherry.move();
		  }
		  
		  if(!pac.eaten)
		  {
			  pac.move();
			  
		  }
		  if(pac.eat)
		  {
			  cly.beScared();
			  ink.beScared();
			  pink.beScared();
			  blink.beScared();
		  }
		  else
		  {
			  cly.calmDown();
			  ink.calmDown();
			  pink.calmDown();
			  blink.calmDown();
		  }
			  
		  cly.move();
		  ink.move();
		  pink.move();
		  blink.move();
		  
		  while(SDL_PollEvent(&eve))
		  {
			  
			  if(eve.type==SDL_QUIT)
				  quit=true;
			  else if(eve.type == SDL_KEYDOWN ) 
			  {
				  start = 1;
				  switch(eve.key.keysym.sym)
				  {
					  case SDLK_UP:
						  pac.sety(-1);
						  break;
					  case SDLK_DOWN:
						  pac.sety(1);
						  break;
					  case SDLK_LEFT:
						  pac.setx(-1);
						  break;
					  case SDLK_RIGHT:
						  pac.setx(1);
						  break;
				  }
			  }
			 
		  }
		  
		  if(SDL_Flip(screen)==-1)
		  {
		  cout<<"SDL_Flip failed!";
		  exit(1);
		  }
	  }

  }
  if(SDL_Flip(screen)==-1)
  {
	  cout<<"SDL_Flip failed!";
	  exit(1);
  }
  
  clean_up();
  
  
  return 0;
}
